package com.crab.c04tree;

/**
 * 最大二叉堆 实现优先队列
 * 出队=移除根节点后，把最后一个叶子节点赋值到根节点，然后下沉
 * 入队=最后一个元素插入，然后上浮，可能需要扩容
 *
 * @author zfd
 * @version v1.0
 * @date 2022/4/29 13:59
 */
public class PriorityQueue {

    public static void main(String[] args) throws Exception {
        PriorityQueue priorityQueue = new PriorityQueue(3);
        priorityQueue.enqueue(1);
        priorityQueue.enqueue(5);
        priorityQueue.enqueue(3);
        priorityQueue.enqueue(8);
        System.out.println("出队：" + priorityQueue.dequeque());
        System.out.println("出队：" + priorityQueue.dequeque());
    }


    private int[] array;
    private int size;

    public PriorityQueue(int capacity) {
        // 初始化长度大小
        this.array = new int[capacity];
    }

    /**
     * 入队
     *
     * @param key
     */
    public void enqueue(int key) {
        if (size >= array.length) {
            // 长度扩容
            resize();
        }
        array[size] = key;
        size++;
        upAdjust();
    }

    /**
     * 出队
     *
     * @return
     * @throws Exception
     */
    public int dequeque() throws Exception {
        if (size <= 0) {
            throw new Exception("队列空");
        }
        // 堆顶
        int head = array[0];
        // 最后一个元素移动到堆顶
        array[0] = array[--size];
        // 下浮处理
        downAdjust();
        return head;
    }

    /**
     * 下沉处理
     */
    private void downAdjust() {
        int parentIndex = 0;
        int temp = array[parentIndex];
        int childIndex = 1;
        while (childIndex < size) {
            // 右孩子
            if (childIndex + 1 < size && array[childIndex + 1] > array[childIndex]) {
                childIndex++;
            }
            // 如果父节点大于任何一个孩子的值 直接跳出
            if (temp > array[childIndex]) {
                break;
            }
            array[parentIndex] = array[childIndex];
            parentIndex = childIndex;
            childIndex = parentIndex * 2 + 1;
        }
        array[parentIndex] = temp;
    }

    /**
     * 上浮调整
     */
    private void upAdjust() {
        int childIndex = size - 1;
        int parentIndex = (childIndex - 1) / 2;
        int temp = array[childIndex];
        while (childIndex > 0 && temp > array[parentIndex]) {
            array[childIndex] = array[parentIndex];
            childIndex = parentIndex;
            parentIndex = (childIndex - 1) / 2;
        }
        array[childIndex] = temp;
    }

    /**
     * 扩容2倍
     */
    private void resize() {
        int[] arrayNew = new int[array.length * 2];
        System.arraycopy(array, 0, arrayNew, 0, array.length);
        array = arrayNew;
    }

}
